package LeetCodeQuestionBank;

import java.util.ArrayList;
import java.util.List;

/**
 *120. 三角形最小路径和
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 输出：11
 * 解释：如下面简图所示：
 *    2
 *   3 4
 *  6 5 7
 * 4 1 8 3
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 * 示例 2：
 *
 * 输入：triangle = [[-10]]
 * 输出：-10
 *
 *
 * 提示：
 *
 * 1 <= triangle.length <= 200
 * triangle[0].length == 1
 * triangle[i].length == triangle[i - 1].length + 1
 * -104 <= triangle[i][j] <= 104
 *
 *
 * 进阶：
 *
 * 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
 */
public class T120 {
    /**
     *解题思路 ； 动态规划 使用状态数组 保存到当前位置的最小和
     *          {  triangle[x][y]+ dp[x-1][y]   y==0
     * f(x,y) = {  triangle[x][y]+ dp[x-1][y-1]   y==x
     *          { Math.min(triangle[x][y]+dp[x-1][y],triangle[x][y]+dp[x-1][y-1])
     */
    public int minimumTotal(List<List<Integer>> triangle) {

        if (triangle.size()==1){
            return triangle.get(0).get(0);
        }

      int[][] dp = new int[triangle.size()][triangle.size()];

        dp[0][0] = triangle.get(0).get(0);


        for (int x = 1; x < triangle.size(); x++) {
            for (int y= 0; y < triangle.get(x).size(); y++) {

                //最左边的数
                if (y==0){

                    dp[x][y] = triangle.get(x).get(y) + dp[x-1][y];

                }else if (y==triangle.get(x).size()-1){
                    //如果时最右边的数
                    dp[x][y] = triangle.get(x).get(y) + dp[x-1][y-1];
                }else {
                    //否则就是中间的数
                    dp[x][y] = Math.min(triangle.get(x).get(y)+dp[x-1][y],triangle.get(x).get(y)+dp[x-1][y-1]);
                }

            }

        }

        //最后遍历 dp最后一行 取最小值
        int min = Integer.MAX_VALUE;
        for (int i = 0; i <dp[triangle.size()-1].length ; i++) {
            min = Math.min(dp[triangle.size()-1][i],min);

        }



        return min;
    }

    public static void main(String[] args) {

        T120 t120 = new T120();
        //[[2],[3,4],[6,5,7],[4,1,8,3]]
        ArrayList<Integer> i0 = new ArrayList<>();
        i0.add(2);
        ArrayList<Integer> i1 = new ArrayList<>();
        i1.add(3);
        i1.add(4);
        ArrayList<Integer> i2 = new ArrayList<>();
        i2.add(6);
        i2.add(5);
        i2.add(7);
        ArrayList<Integer> i3 = new ArrayList<>();
        i3.add(4);
        i3.add(1);
        i3.add(8);
        i3.add(3);

        List<List<Integer>> arrayLists = new ArrayList<>();

        arrayLists.add(i0);
        arrayLists.add(i1);
        arrayLists.add(i2);
        arrayLists.add(i3);

        int i = t120.minimumTotal(arrayLists);


    }
}
